package cn.walls1717.dataStructure.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author walls1717
 * @since 2022-04-29
 **/
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void insertionSort(int[] arr) {
        // 临时变量，存储待插入值
        int temp;
        // 控制已排序区域循环
        int j;
        for (int i = 1; i < arr.length; ++i) {
            temp = arr[i];
            j = i - 1;
            while (j >= 0) {
                if (temp < arr[j]) {
                    // 如果待插入值比已排序区域中的元素小
                    // 那么就向后移动已排序区域中的元素
                    // 给待插入值腾出位置
                    arr[j+1] = arr[j];
                } else {
                    // 待插入值没有比已排序区域中元素小
                    // 那么直接结束循环，找下一个待插入值比较
                    break;
                }
                --j;
            }
            // 已排序区域循环完毕，将待插入值放入腾出来的位置
            arr[j+1] = temp;
        }
    }
}
